/*
给定一个整数数组，找出其中两个数满足相加等于你指定的目标数字。

要求：这个函数twoSum必须要返回能够相加等于目标数字的两个数的索引，且index1必须要小于index2。请注意一点，你返回的结果（包括index1和index2）都不是基于0开始的。

你可以假设每一个输入肯定只有一个结果。

举例：

输入：numbers={2, 7, 11, 15}, target = 9

输出：index1 = 1, index2 = 2(不是基于0开始的)
*/
#include <iostream>
#include <map>
#include <string>
#include <deque>
#include <stack>
#include <vector>

std::vector<int> twoSum(std::vector<int> arr, int target)
{
    std::vector<int> rst;
    if (arr.size() <= 0) {
        return rst;
    }
    std::map<int, int> m;
    for (int i = 0; i != arr.size(); ++i) {
        m[arr[i]] = i;
    }
    std::map<int, int>::iterator itrMap;
    for (int i = 0; i != arr.size(); ++i) {
        int tmp = target - arr[i];
        itrMap = m.find(tmp);
        if (itrMap != m.end()) {
            if (itrMap->second == i) {
                continue;
            } else {
                rst.emplace_back(i + 1);
                rst.emplace_back(itrMap->second + 1);
                return rst;
            }
        }
    }
    return rst;
}

int main(int argc, const char * argv[])
{
    std::vector<int> arr = {2,7,11,15};
    std::vector<int> rst =  twoSum(arr, 9);
    return 0;
}
